/*!
 Temelia - Tree algorithms implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with this program; if not, write to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/common.h"

#include "include/linked_list.h"
#include "include/iterator.h"

#include "include/vector.h"

#include "include/tree_algorithms.h"
#include "include/queue.h"
#include <stdlib.h>

static void _queue_pusher(void *key, void *context);

void tree_bfs_iterate(tree_t tree, void key_handler(void *x, void *context),
		void *context)
{
	queue_t queue;
	tree_t current_node;

	LOGGER("[tree bfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
			tree, key_handler, context);

	_ASSERT(tree, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	queue = queue_new(DEFAULT_SIZE);
	queue_push_back(queue, tree);

	while (!queue_is_empty(queue))
	{
		current_node = queue_get_front(queue);
		queue_pop_front(queue);
		key_handler(tree_get_key(current_node), context);

		if (tree_get_type(current_node))
			linked_list_iterate(tree_get_children(current_node),
					_queue_pusher, queue, 1);
		else
			vector_iterate(tree_get_children(current_node), _queue_pusher,
					queue);
	}

	queue_delete(queue);
}

void tree_dfs_iterate(tree_t tree, void key_handler(void *x, void *context),
		void *context)
{
	linked_list_iterator_t it;
	int i, size;
	void *children;

	LOGGER("[tree dfs travel] tree=\"%p\" key_handler=\"%p\" context=\"%p\"\n",
			tree, key_handler, context);

	_ASSERT(tree, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	key_handler(tree_get_key(tree), context);
	children = tree_get_children(tree);

	if (tree_get_type(tree))
	{
		for (it = linked_list_get_begin(children); it != NULL; it
				= linked_list_iterator_get_next(it))
			tree_dfs_iterate(linked_list_iterator_get_key(it), key_handler,
					context);
	}
	else
	{
		size = vector_get_size(children);

		for (i = 0; i < size; i++)
			tree_dfs_iterate(vector_get_key_at(children, i), key_handler,
					context);
	}
}

void _queue_pusher(void *key, void *context)
{
	LOGGER("[tree bfs travel] _queue_pusher key=\"%p\" context=\"%p\"", key,
			context);
	queue_push_back(context, key);
}
